package com.njupt.Tree;



import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/2 8:57
 * @Description: 112. 路径总和
 * @Version: 1.0
 */


public class HasPathSum {

    /**
     * 后续遍历非递归算法
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum1(TreeNode root, int targetSum) {
        Deque<TreeNode> treeStack = new LinkedList<>();
        Deque<Boolean> flagStack = new LinkedList<>();
        Boolean flag = false;
        TreeNode cur = root;

        while(cur != null || !treeStack.isEmpty()){

            if(cur != null){
                treeStack.push(cur);
                flagStack.push(false);
                cur = cur.left;
            }else {
                cur = treeStack.pop();
                flag = flagStack.pop();
                if(flag == false){
                    treeStack.push(cur);
                    flagStack.push(true);
                    cur = cur.right;
                }else {
                    //访问节点
                    if(cur.left == null && cur.right == null){
                        int sum = cur.val;
                        Iterator<TreeNode> iterator = treeStack.iterator();
                        while(iterator.hasNext()){
                            sum += iterator.next().val;
                        }
                        if(sum == targetSum){
                            return true;
                        }
                    }
                    cur = null;
                }
            }
        }
        return false;

    }

    /**
     * 递归算法
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum){
        List<Integer> results = new ArrayList<>();
        if(root == null) return false;
        return isPathSum(root,results,targetSum);

    }

    private boolean isPathSum(TreeNode root, List<Integer> results, int targetSum) {
        results.add(root.val);
        if(root.left == null && root.right == null){
            int sum = 0;
            for (int i = 0; i < results.size(); i++) {
                sum += results.get(i);
            }
            if(sum == targetSum){
                return true;
            }
            return false;
        }
        boolean left = false;
        if(root.left != null){
            left = isPathSum(root.left, results, targetSum);
            results.remove(results.size()-1);

        }
        boolean right = false;
        if(root.right != null){
            right = isPathSum(root.right, results, targetSum);
            results.remove(results.size()-1);
        }

        return left || right;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(6);
        root.left.left.right = new TreeNode(2);
        root.right.right.right = new TreeNode(1);

//
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
        HasPathSum test = new HasPathSum();
        boolean b = test.hasPathSum(root,22);
        System.out.println(b);



    }
}
